#pragma once
#include "TreeNode.h"

template <class NodeType>
class QuadTree
{
public:
	typedef bool(TreeNode::*pSearchFunc)();

	QuadTree(void) { mRoot = new NodeType; };
	virtual ~QuadTree(void) {};

	void createEmptyTree(int layer);
	void postOrder(pSearchFunc) const;
	void appendLeafNode(int layer, int idx, TreeNode* leaf);

	TreeNode* getRoot() const {return mRoot;}
private:
	// function
	void createTree(int& curLayer, int totalLayer, TreeNode* rootNode);
	void appendLeaf(int &curLayer, int layer, int idx, int fidx, TreeNode* leaf, TreeNode* father);
private:
	TreeNode* mRoot;
};

template <class NodeType>
void QuadTree<NodeType>::createEmptyTree(int layer)
{
	int initialLayer = 0;
	createTree(initialLayer,layer,mRoot);
}

template <class NodeType>
void QuadTree<NodeType>::createTree( int& curLayer, int totalLayer, TreeNode* rootNode )
{
	if (++curLayer > totalLayer)
	{
		--curLayer;
		return;
	}
	for (int i=0; i<4; ++i)
	{
		TreeNode* node = new NodeType;
		rootNode->addChild(i,node);
		createTree(curLayer,totalLayer,node);
	}
	--curLayer;
}

template <class NodeType>
void QuadTree<NodeType>::appendLeafNode( int layer, int idx, TreeNode* leaf )
{
	int curLayer = 0;
	appendLeaf(curLayer,layer,idx,0,leaf,mRoot);
}

template <class NodeType>
void QuadTree<NodeType>::appendLeaf( int &curLayer, int layer, int idx, int fidx, TreeNode* leaf, TreeNode* father )
{
	if (curLayer == layer)
	{
		int index = idx % 4;
		father->addChild(index,leaf);
	}
	else
	{
		int layeridx = (int)(idx / (pow(4.0,layer-curLayer))); // give you index of this layer
		//if (fidx > 0)
		//{
			layeridx = layeridx%4;
		//}
		++curLayer;
		appendLeaf(curLayer,layer,idx,layeridx,leaf,father->getChild(layeridx));
	}
}

template <class NodeType>
void QuadTree<NodeType>::postOrder( pSearchFunc ) const
{
	mRoot->postOrder(pSearchFunc);
}